package leetcode_100;

/**
 *@author 周杨
 *MinimumPathSum_64  Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Example:

Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.
 *describe: 动态规划 AC 52%
 *2018年5月10日 下午3:58:05
 */
public class MinimumPathSum_64 {

	public static void main(String[] args) {
		MinimumPathSum_64 test=new MinimumPathSum_64();
		int grid[][]=new int[][] {{1,3,1},{1,5,1},{4,2,1}};
		System.out.println(test.minPathSum(grid));

	}
	
	public int minPathSum(int[][] grid) {
        if(grid.length==0)
        	return 0;
        if(grid[0].length==0)
        	return 0;
        int row=grid.length;
        int col=grid[0].length;
        int [][]help=new int[row][col];
        help[0][0]=grid[0][0];
        for(int i=1;i<col;++i) 
        	help[0][i]=help[0][i-1]+grid[0][i];
        for(int i=1;i<row;++i)
        	help[i][0]=help[i-1][0]+grid[i][0];
        for(int i=1;i<row;++i)
        	for(int j=1;j<col;++j) {
        		help[i][j]=Math.min(help[i-1][j]+grid[i][j], help[i][j-1]+grid[i][j]);
        	}
        return help[row-1][col-1];
    }

}
